package algorithms.leaning.class12;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * 判断二叉树是否完全二叉树
 * 每层都是满的，否则也是从左到右依次变满
 *
 * @author guichang
 * @date 2021/6/12
 */

@SuppressWarnings("all")
public class Code1_二叉树_完全二叉树 {

    public static void main(String[] args) {
        TreeNode treeNode = MyUtil.createTreeNode(1, 2, null, null, 3, 4, 5);
        MyUtil.print(isCBT2(treeNode));
    }

    /**
     * 常规解法，层序遍历 TODO
     * 条件1: 有右节点无左节点直接返回false
     * 条件2: 遇到左右节点不双全的情况下, 后续的节点应该都是叶子节点（左右节点孩子均为空）
     */
    public static boolean isCBT1(TreeNode head) {
        return false;
    }

    /**
     * 递归套路
     */
    public static boolean isCBT2(TreeNode head) {
        return process(head).isCBT;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(true, true, 0);
        }

        Info li = process(node.left);
        Info ri = process(node.right);
        int height = Math.max(li.height, ri.height) + 1;
        boolean isFBT = li.isFBT && ri.isFBT && (li.height - ri.height == 0);
        boolean isCBT = false;
        // 左满，右满，高度差 <= 1
        if (li.isFBT && ri.isFBT && (li.height - ri.height <= 1)) {
            isCBT = true;
        }
        // 左完全，右满，高度差 = 1
        if (li.isCBT && ri.isFBT && (li.height - ri.height == 1)) {
            isCBT = true;
        }
        // 左满，右完全，高度差 = 0
        if (li.isFBT && ri.isCBT && (li.height - ri.height == 0)) {
            isCBT = true;
        }
        return new Info(isCBT, isFBT, height);
    }

    private static class Info {
        boolean isCBT; // 是否完全二叉树
        boolean isFBT; // 是否满二叉树
        int height; // 树高度

        public Info(boolean isCBT, boolean isFBT, int height) {
            this.isCBT = isCBT;
            this.isFBT = isFBT;
            this.height = height;
        }
    }


}